package com.coolingme.algo_01_list.reverselist;

/**
 * 翻转链表
 *
 * @author wangyue
 * @date 2020/10/30 13:53
 */
public class ReverseLinkedList {

    /**
     * 翻转单项链表
     *
     * @param head 头节点
     * @return 翻转后的单项链表
     */
    public static LinkedListNode reverse(LinkedListNode head) {
        if (head == null) {
            return null;
        }
        // 赋值
        LinkedListNode pre = head;
        LinkedListNode current = head.next;
        // 开始移动
        pre.next = null;
        while (current != null) {
            // 设置下一个节点
            LinkedListNode next = current.next;
            // 翻转,设置上一个节点为当前节点的下一个节点
            current.next = pre;
            // 整体向后移
            pre = current;
            current = next;
        }
        return pre;
    }

    /**
     * 翻转单向链表指定范围内的数据
     *
     * @param head 头节点
     * @param m    起始位置
     * @param n    结束位置
     * @return 翻转后的单项链表
     */
    public static LinkedListNode reverse(LinkedListNode head, Integer m, Integer n) {
        // 未判断链表长度是否足够
        if (head == null || m >= n) {
            return null;
        }
        // 创建哨兵并连接链表
        LinkedListNode dummy = new LinkedListNode(-1);
        dummy.next = head;
        // 将头结点设置为哨兵
        head = dummy;
        // 将head节点指向起始位置
        for (int i = 1; i < m; i++) {
            System.out.print(i + "  ");
            head = head.next;
        }
        // preM节点为 m节点的上一个节点，先给一个初始值
        LinkedListNode preM = head;
        // m节点为preM节点的下一个节点
        LinkedListNode mNode = preM.next;
        // n节点设置为m同一位置
        LinkedListNode nNode = mNode;
        // n的下一个节点
        LinkedListNode postN = nNode.next;

        // 翻转m到n之间的数据
        for (int i = m; i < n; i++) {
            LinkedListNode nextPostN = postN.next;
            // 翻转
            postN.next = nNode;
            // 后移
            nNode = postN;
            postN = nextPostN;
        }

        // 连接 m到n 翻转之后的数据
        mNode.next = postN;
        preM.next = nNode;

        // 返回头结点
        return dummy.next;
    }

    public static void main(String[] args) {
        LinkedListNode node = new LinkedListNode(1);
        LinkedListNode node2 = node.setNext(2);
        LinkedListNode node3 = node2.setNext(3);
        LinkedListNode node4 = node3.setNext(4);
        LinkedListNode node5 = node4.setNext(5);
        LinkedListNode node6 = node5.setNext(6);
        LinkedListNode node7 = node6.setNext(7);
        node7.setNext(8);

        System.out.println("input: " + node.toString());

        // 翻转
        LinkedListNode reverseNode = reverse(node);
        System.out.println("output: " + reverseNode.toString());

        System.out.println("-------------------------------");


        node = reverse(reverseNode);

//        int m = 3;
//        int n = 6;
        int m = 1;
        int n = 8;
        System.out.println(String.format("input: %s ,m = %d ,n = %d", node.toString(), m, n));

        // 翻转
        LinkedListNode reverseNode2 = reverse(node, m, n);
        System.out.println("output: " + reverseNode2.toString());
    }

}
